/*
 * @Author: gitee_com_zb
 * @Date: 2024-11-14 16:16:57
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-11-14 16:17:09
 * @FilePath: /lzb/GiteeCode/algorithm/优选算法36.只出现一次的数字II(medium).cpp
 * @Description: 题目链接: https://leetcode.cn/problems/single-number-ii
 */

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 1. 哈希统计
        // unordered_map<int,int> hash;
        // int ret = 0;
        // for(const auto& x : nums) hash[x]++;
        // for(const auto& [k,v] : hash) {
        //     if(v == 1) {ret = k; break;}
        // }
        // return ret;
        
        // 2. 位运算解决
        // 每一bit位所有数的和相加%3,余下的1就是出现一次的数对应位置上的1
        int ret = 0;
        for(int i = 0; i < 32; i++) {
            int sum = 0;
            for(const auto& x : nums) {
                if(x & (1 << i)) sum++;
            }
            sum %= 3;
            if(sum == 1) ret |= (1 << i);
        }
        return ret;
    }
};